#include <complex>
#include <cstddef>
#include <numbers>
#include <vector>

namespace WinstJackonw {

using Complex = std::complex<double>;
using ComplexArray = std::vector<Complex>;

// NOLINTNEXTLINE(misc-no-recursion)
inline void fft_radix2_rec(ComplexArray& in) {
  std::size_t len = in.size();
  if (len == 1) return;
  if (len == 2) {
    auto tmp1 = in[0];
    auto tmp2 = in[1];
    in[0] = tmp1 + tmp2;
    in[1] = tmp1 - tmp2;
  }
  auto mid = len / 2;
  ComplexArray arrLeft(mid);
  ComplexArray arrRight(mid);
  for (std::size_t i{0}; i < mid; i++) {
    arrLeft[i] = in[2 * i];
    arrRight[i] = in[2 * i + 1];
  }
  fft_radix2_rec(arrLeft);
  fft_radix2_rec(arrRight);
  Complex omega(1, 0);
  Complex unit = std::polar<double>(1, 2 * std::numbers::pi / (double)len);
  for (std::size_t i{}; i < mid; i++) {
    Complex tmp1 = arrLeft[i];
    Complex tmp2 = arrRight[i] * omega;
    in[i] = tmp1 + tmp2;
    in[i * 2 + 1] = tmp1 - tmp2;

    omega *= unit;
  }
}
}  // namespace WinstJackonw